package com.chengqs.leetcode.hot100;

import com.chengqs.leetcode.utils.DataGeneratorUtil;
import com.chengqs.leetcode.utils.TimeCostUtil;

import java.util.*;

/**
 * 子串<br>
 * 队列、数组、滑动窗口<br>
 * 困难
 *
 * <h1>239. 滑动窗口最大值</h1>
 *
 * <p>给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。</p>
 *
 * <p>返回 滑动窗口中的最大值 。</p>
 */
public class D11MaxSlidingWindow {
    public static void main(String[] args) {
        D11MaxSlidingWindow maxSlidingWindow = new D11MaxSlidingWindow();
        int[] nums = {1,3,-1,-3,5,3,6,7};

        TimeCostUtil.timeCost("优先队列", () -> maxSlidingWindow.solution1(nums, 3));
        TimeCostUtil.timeCost("单调队列", () -> maxSlidingWindow.solution2(nums, 3));
        TimeCostUtil.timeCost("分块 + 预处理", () -> maxSlidingWindow.solution3(nums, 3));

        System.out.println("大数据量");
        int[] nums2 = DataGeneratorUtil.generateRandomIntArray(1000000, -50, 50);
        TimeCostUtil.timeCost("优先队列", () -> maxSlidingWindow.solution1(nums2, 50));
        TimeCostUtil.timeCost("单调队列", () -> maxSlidingWindow.solution2(nums2, 50));
        TimeCostUtil.timeCost("单调队列", () -> maxSlidingWindow.solution2_2(nums2, 50));
        TimeCostUtil.timeCost("分块 + 预处理", () -> maxSlidingWindow.solution3(nums2, 50));

    }

    // 方法一：优先队列
    public int[] solution1(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] pair1, int[] pair2) {
                // 如果值不同，按值排序，如果值相同，按索引排序
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
            }
        });
        for (int i = 0; i < k; ++i) {
            // 1索引存值，二索引存索引
            pq.offer(new int[]{nums[i], i});
        }
        int[] ans = new int[n - k + 1];
        ans[0] = pq.peek()[0];
        for (int i = k; i < n; ++i) {
            // 向队列中添加元素
            pq.offer(new int[]{nums[i], i});
            while (pq.peek()[1] <= i - k) {
                // 延迟删除：不立即删除所有过期元素，只在需要获取最大值时检查堆顶是否过期
                pq.poll();
            }
            // 获取最大值
            ans[i - k + 1] = pq.peek()[0];
        }
        return ans;
    }

    // 方法二：单调队列
    public int[] solution2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new LinkedList<Integer>();
        // 初始化第一个窗口 (0 到 k-1)
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast(); // 移除比当前元素小的元素索引
            }
            deque.offerLast(i); // 添加当前元素索引
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()]; // 队首是当前窗口最大值

        // 处理后续窗口 (k 到 n-1)
        for (int i = k; i < n; ++i) {
            // 维护单调性：移除队尾比当前元素小的索引
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 移除超出窗口范围的索引
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()]; // 当前窗口最大值
        }
        return ans;
    }

    public int[] solution2_2(int[] nums, int k) {
        int n = nums.length;
        Deque<Integer> deque = new ArrayDeque<>();
        // 初始化第一个窗口 (0 到 k-1)
        for (int i = 0; i < k; ++i) {
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast(); // 移除比当前元素小的元素索引
            }
            deque.offerLast(i); // 添加当前元素索引
        }

        int[] ans = new int[n - k + 1];
        ans[0] = nums[deque.peekFirst()]; // 队首是当前窗口最大值

        // 处理后续窗口 (k 到 n-1)
        for (int i = k; i < n; ++i) {
            // 维护单调性：移除队尾比当前元素小的索引
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }
            // 移除超出窗口范围的索引
            deque.offerLast(i);
            while (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            ans[i - k + 1] = nums[deque.peekFirst()]; // 当前窗口最大值
        }
        return ans;
    }

    // 方法三：分块 + 预处理
    public int[] solution3(int[] nums, int k) {
        int n = nums.length;
        // 前缀最大值数组：prefixMax[i] 表示从当前块的开始到i位置的最大值
        int[] prefixMax = new int[n];
        // 后缀最大值数组：suffixMax[i] 表示从i位置到当前块结束的最大值
        int[] suffixMax = new int[n];

        // 计算前缀最大值
        for (int i = 0; i < n; ++i) {
            if (i % k == 0) {
                // 当前是块的起始位置，最大值就是自己
                prefixMax[i] = nums[i];
            } else {
                // 不是块的起始，就和前一个位置比较取最大值
                prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
            }
        }

        // 计算后缀最大值（从后往前算）
        for (int i = n - 1; i >= 0; --i) {
            if (i == n - 1 || (i + 1) % k == 0) {
                // 当前是块的结束位置（包括数组末尾），最大值就是自己
                suffixMax[i] = nums[i];
            } else {
                // 不是块的结束，就和后一个位置比较取最大值
                suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
            }
        }

        // 结果数组：有 n-k+1 个窗口
        int[] ans = new int[n - k + 1];
        for (int i = 0; i <= n - k; ++i) {
            // 关键：窗口 [i, i+k-1] 的最大值 =
            // max(从i开始的后缀最大值, 到i+k-1结束的前缀最大值)
            ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
        }
        return ans;
    }
}
